import java.util.*;
public class test {
    //leetcode 面试题01.02.判定是否互为字符重排
    public boolean CheckPermutation(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        if (len1 != len2) {
            return false;
        }
        HashMap<Character, Integer> map1 = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();
        for (int i = 0; i < len1; i++) {
            map1.put(s1.charAt(i), map1.getOrDefault(s1.charAt(i), 0) + 1);
            map2.put(s2.charAt(i), map2.getOrDefault(s2.charAt(i), 0) + 1);
        }
        for (char i = 'a'; i <= 'z'; i++) {
            if (map1.containsKey(i) && map2.containsKey(i)) {
                if (!map1.get(i).equals(map2.get(i))) {
                    return false;
                }
            } else if ((!map1.containsKey(i) && map2.containsKey(i)) || (map1.containsKey(i) && !map2.containsKey(i))) {
                return false;
            }
        }
        return true;
    }
    //leetcode 1046.最后一块石头的重量
    class Solution {
        class ImpCmp implements Comparator<Integer> {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        }
        public int lastStoneWeight(int[] stones) {
            int n = stones.length;
            if (n == 1)
                return stones[0];
            if (n == 2)
                return Math.abs(stones[0] - stones[1]);
            Arrays.sort(stones);// 递归的结束条件，如果【排序】后倒数第三个元素为0，说明只剩两个石头，直接返回最后一个减倒数第二个
            if (stones[n - 3] == 0) {
                return stones[n - 1] - stones[n - 2];
            }
            // 直接操作原数组，最后一块等于它减去前一块，被粉粹的直接置0，这两步绝了
            stones[n - 1] = stones[n - 1] - stones[n - 2];
            stones[n - 2] = 0;
            return lastStoneWeight(stones);
        }
    }
    //leetcode 671.二叉树中第二小的节点
    class Solution {
        public int min = -1;
        public int findSecondMinimumValue(TreeNode root) {
            findMin(root, root.val);
            return min;
        }
        public void findMin(TreeNode root, int a) {
            if (root == null) {
                return;
            }
            if (root.val != a) {
                if (min == -1) {
                    min = root.val;
                } else {
                    if (root.val < min && root.val > a) {
                        min = root.val;
                    }
                }
            }
            findMin(root.left, a);
            findMin(root.right, a);
        }
    }
    //leetcode 1160.拼写单词
    class Solution {
        public int countCharacters(String[] words, String chars) {
            HashMap<Character, Integer> map1 = new HashMap<>();
            int len = 0;
            for (int i = 0; i < chars.length(); i++) {
                char c = chars.charAt(i);
                map1.put(c, map1.getOrDefault(c, 0) + 1);
            }
            for (int i = 0; i < words.length; i++) {
                HashMap<Character, Integer> map = new HashMap<>();
                String s = words[i];
                boolean count = true;
                for (int j = 0; j < s.length(); j++) {
                    char c1 = s.charAt(j);
                    map.put(c1, map.getOrDefault(c1, 0) + 1);
                }
                for (char k = 'a'; k <= 'z'; k++) {
                    if (map.containsKey(k) && map1.containsKey(k)) {
                        if (map.get(k) > map1.get(k)) {
                            count = false;
                            break;
                        }
                    } else if (map.containsKey(k) && !map1.containsKey(k)) {
                        count = false;
                        break;
                    }
                }
                len += (count ? s.length() : 0);
            }
            return len;
        }
    }
    //leetcode 1154.一年中的第几天
    class Solution {
        public static int dayOfYear(String date) {
            int n = 0;
            int year = Integer.valueOf(date.substring(0, 4));
            int month = Integer.valueOf(date.substring(5, 7));
            int day = Integer.valueOf(date.substring(8, 10));
            int[] months = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
            if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) {
                months[2] = 29;
            }
            for(int i = 1;i < month;i++){
                n += months[i];
            }
            n += day;
            return n;
        }
    }
}
